The present invention relates to methods for processing images and for generating chain code representations of images.
A configuration of pixels in an image may be represented as a series of vectors. Each vector represents a unit displacement in a predetermined direction and is referred to as a chain element. The series of vectors is called an "indexed sequence" or "chain code." The coordinates of each connected point are called chain coordinates.
The process of expressing an image as a series of vectors is generally called "chain coding." Chain coding is useful for representing images using a minimum amount of storage.
FIG. 1 illustrates a conventional method for generating a chain code representation of a configuration in an image. A pixel representation is scanned in a raster scan order. The first configuration pixel encountered during scanning, designated as pixel A, serves as the starting point for the chain code representation. The chain code representation will be a series of vectors tracing the boundary of the configuration in a clockwise or anti-clockwise direction. A method for tracing the boundary in an anti-clockwise direction is described as a series of steps as follows.
(a) Pixels around A are searched to locate another pixel of the configuration. Searching begins with the pixel below and to the left of pixel A and advances in an anti-clockwise direction. Since a line above A was previously scanned, no pixels of the configuration exist above A. Since a line is scanned from left to right, no pixels of the configuration exist to the left of A. In the example of FIG. 1, the pixel below and to the left of pixel A (in the direction labeled al) is evaluated first, but is not a pixel of the configuration. Advancing in an anti-clockwise direction, the pixel below pixel A (in a direction labeled a2) is evaluated second. This second pixel is part of the configuration, and is labeled as pixel B.
(b) Pixels around B are searched to locate another pixel of the configuration. Searching begins with the pixel to the left of B when the direction from pixel A to pixel B is downward. (The upward pixel A need not be searched, and the location to the left of A was evaluated before locating A as a starting point.) Searching advances in an anti-clockwise direction. In the illustration of FIG. 1, a pixel of the configuration below and to the left of B would be found. That pixel is labeled as pixel C.
(c) After each new pixel is located, searching continues around the new pixel. When the new pixel is located in a horizontal or vertical direction from the previous pixel, searching begins from a pixel which is located two pixels around from previous pixel in the anti-clockwise direction. When the new pixel is located in a diagonal direction from the previous pixel, searching begins from a pixel which is located three pixels around from the previous pixel in the anti-clockwise direction. The chain code is completed when the process returns to pixel A.
(d) After completing a chain code representation for the configuration, the method resumes scanning the image in raster scan order beginning with pixel X (in search of a new configuration).
As can be recognized from the process described above, an image stored as raw pixel values is an inconvenient form from which to generate a chain code representation.